#include <iostream>

using std::cout;

struct ListNode
{
    int val;
    struct ListNode* next;
    ListNode(int val):val(val),next(nullptr){}
};

class Solution {
public:
    static ListNode* removeNthFromEnd(ListNode* head, int n) {
        if(n < 0) return head;

        ListNode* dummyHead = new ListNode(0);
        dummyHead->next = head;
        ListNode* slow = dummyHead;
        ListNode* fast = dummyHead;
        int tmpN = n;
        while (tmpN -- >= 0) // 要多走一步
        {
            if(fast == nullptr) break;

            fast = fast->next;
        }

        if(tmpN > -1 && fast == nullptr) return head;
        while (fast != nullptr)
        {
            fast = fast->next;
            slow = slow->next;
        }

        ListNode* tmp = slow->next;
        slow->next = tmp->next;
        delete tmp;

        head = dummyHead->next;
        delete dummyHead;
        return head;
    }
};


int main(int argc, char const *argv[])
{
    ListNode* head = new ListNode(1);
    for(int i = 0;i < 0;++ i)
    {
        ListNode* newNode = new ListNode(i + 2);
        newNode->next = head->next;
        head->next = newNode;
    }
    ListNode* cur = head;
    cout << cur->val << "\n";
    while (cur != nullptr)
    {
        cout << cur->val;
        cur = cur->next;
    }
    cout << "\n\n";
    cur = Solution::removeNthFromEnd(head,2);

    while (cur != nullptr)
    {
        cout << cur->val;
        cur = cur->next;
    }


    getchar();
    return 0;
}
